package 剑指Offer._5160;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/15 16:24
 * 两个链表的第一个公共节点
 * 输入两个链表，找出它们的第一个公共节点。
 * 算法：链表
 * 先遍历第一个链表，用哈希表存储该链表的节点，
 * 再遍历第二个链表，如果哈希表中存在节点，就返回
 * -----------------------------------------
 * 假如两个链表有交集，那么 a + c + b = b + c + a
 * 就算没有交集，那么 a + b = b + a
 */
public class _52 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode c1 = headA, c2 = headB;
        // 就算没有交集，最后退出循环的条件是 c1 = c2 = null
        while (c1 != c2) {
            c1 = c1 == null ? headB : c1.next;
            c2 = c2 == null ? headA : c2.next;
        }
        return c1;
    }

}
